package complexite;

import java.util.Collections;

public class QuickSelect2 {
	
	public static void faireTriInsertion(ExtArrayList az){
	    boolean bRetour = false;
	    int cpt;
	    int i;
	    int lg;
	    int Val;
	    lg = az.size();
	    
	    for(i = 1; i < lg ; i++)
	    {    
	        Val = az.get(i);
	        cpt = i-1;
	        do
	        {
	            bRetour = true;
	            if(az.get(cpt) > Val)
	          {    
	            	az.set(cpt+1,az.get(cpt));
	                cpt = cpt-1;
	                bRetour = false;
	            }
	            if(cpt <0)
	            {
	                bRetour = true;
	            }
	        }while(!bRetour);
	        az.set(cpt+1,Val);     
	    }
	}
	
	public static void echange (ExtArrayList az,int num1,int num2){
		Collections.swap(az, num1,num2);
	}
	
	public static int Selection (ExtArrayList a,int p, int r,int i){
		System.out.println("Selection(),debut a:" +a);
		System.out.println("Selection(),debut p=" +p + "  r=" + r +"  i="+ i);
		if(p==r){
			System.out.println("Selection(),p=r  a.get(p) = " + a.get(p));
			return a.get(p);
		}
		
		//int piv= p + new Random().nextInt((r - p) + 1);
		int piv = bon_pivot(a);
		System.out.println("Selection(),piv=" + piv);
		
		int q = partitionRand(a,p,r,piv);
		System.out.println("Selection(),q=" + q);
		
		int k=q-p+1;
		System.out.println("Selection(),rang du pivot=" +k);
		
		if(i==k){
			System.out.println("Selection(),i=k  a.get(q)=" +a.get(q));
			return a.get(q);	
		}
		else if(i<k){
			System.out.println("Selection(),i<k");
			return Selection(a, p, q-1, i);
		}
		else{
			System.out.println("Selection(),i>=k");
			return Selection(a, q+1, r, i-k);
		}
	}
	
	public static int partitionRand (ExtArrayList a, int p,int r,int piv){
		
		System.out.println("partition() debut" + a);
		System.out.println("partition() debut,p=" + p + "  r=" + r + "  piv" + piv );
		
		//piv est une valeur, il nous fo sont indice dans le tableau
		piv = a.lastIndexOf(piv);
		System.out.println("partition(), index de piv" + piv );
		
		echange(a,r,piv);
		System.out.println("partition(), apres l'echange" + a);
		int x=a.get(r);
		int i=p-1;
		
		for(int j=p;j<r;j++){
			if(a.get(j) < x){
				i++;
				echange(a,i,j);
			}
		}
		echange(a,i+1,r);
		System.out.println("partition() fin" + a);
		return i+1;
	}
	
	
	public static int bon_pivot(ExtArrayList a){
		
		
//		try {
//			Thread.sleep(2000);
//		} catch (InterruptedException e) {
//			// TODO Auto-generated catch block
//			e.printStackTrace();
//		}
		
		
		System.out.println("bon_pivot() debut");
		ExtArrayList bloc ;
		ExtArrayList medmed = new ExtArrayList();
		
		if(a.size() > 5){
			System.out.println("bon_pivot() size of array > 5");
			//pour chaque group de 5
			for( int i=0; i<a.size()-5 ;i+=5){	
				//on decoupe en block de 5
				bloc=new ExtArrayList(a.subList(i,i+5));
				//on tri le block
				faireTriInsertion(bloc);
				//on recup la mediane du block et la rajoute dans medmed
				// 0 1 2 3 4
				medmed.add(bloc.get(2));
			}
		}
		else{
			System.out.println("bon_pivot() size of array <= 5");
			faireTriInsertion(a);
//			System.out.println("bon_pivot() " + a);
			//medmed.add(a.get((a.size() + 1) / 2 - 1));
			return a.get((a.size() + 1) / 2);
		}
		
		
		
//		System.out.println("valeur des médians :"+medmed);
		//System.out.println("fin bon_pivot()");
		return Selection ( medmed,0, medmed.size() - 1, (medmed.size() + 1) / 2);
	}
	
	
	
	
	
	public static void main (String args[]){
		ExtArrayList az = new ExtArrayList();
		az.getArray(5, 10, 30);
		System.out.println("de base     : " +az);
		//System.out.println(Selection(az,0,az.size()-1,(az.size() + 1) / 2 -1));
		System.out.println(Selection(az,0,az.size()-1,2));
		System.out.println("apres select: " + az);
		faireTriInsertion(az);
		System.out.println("apres tri   : " + az);
	}
	
	
}
